package a07_二叉树;

/**
 * <p>
 * a11_完全二叉树的节点个数复习0
 * </p>
 *
 * 叶子节点是连续的
 *
 * 完全二叉树节点数量：2<<(层数-1) + 1=
 * 1->1 2<<0 + 1
 * 2->3 2<<1 + 1
 * 3->7
 *
 * @author flyduck
 * @since 2024/12/27
 */
public class a11_完全二叉树的节点个数复习0 {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }

        TreeNode leftNode = root;
        int leftHeight = 1;
        while (leftNode != null) {
            leftNode = leftNode.left;
            leftHeight++;
        }

        TreeNode rightNode = root;
        int rightHeight = 0;
        while (leftNode != null) {
            rightNode = rightNode.right;
            rightHeight++;
        }

        if (leftHeight == rightHeight) {
            return 2 << (leftHeight - 1) + 1;
        }else {
            int leftNodes = countNodes(root.left);
            int rightNodes = countNodes(root.right);
            return leftNodes + rightNodes + 1;
        }

    }
}
